/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (!list1)  return list2;
    if (!list2)  return list1;

    ListNode* head, * tail;
    head = tail = (ListNode*)malloc(sizeof(ListNode));

    ListNode* h1 = list1, * h2 = list2;

    while (h1 && h2)
    {
        if (h1->val < h2->val)
        {

            tail->next = h1;
            tail = tail->next;
            h1 = h1->next;
        }
        else
        {
            tail->next = h2;
            tail = tail->next;
            h2 = h2->next;
        }
    }

    if (h1)
        tail->next = h1;
    if (h2)
        tail->next = h2;

    ListNode* ret = head->next;
    free(head);
    head = tail = NULL;

    return ret;
}